//
// Created by Administrator on 2021/5/8.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>

using namespace std;

class Solution {
private:
    int minTime = INT_MAX;
public:
    int minimumTimeRequired(vector<int> &jobs, int k) {
        vector<int> workTime(k, 0); // 每个工人的工作时间
//        sort(jobs.rbegin(),jobs.rend());   // 给每项任务需要的时间排序 从大到小
        auto n = (int) jobs.size() - 1;
        // 暴力dfs 给出所有的方案
        backtrack(jobs, workTime, n);
        return minTime;
        // 问题： 重复的方案太多了
    }

    void backtrack(vector<int> &jobs, vector<int> &workTime, int n) {
        if (n == -1) {
            minTime = min(minTime, *max_element(workTime.begin(), workTime.end()));
            return;
        }
        for (int i = 0; i < workTime.size(); ++i) { // 把第n件任务交给第i个工人
            workTime[i] += jobs[n];
            backtrack(jobs, workTime, n - 1);
            workTime[i] -= jobs[n];
        }
    }
};

class Solution2 {  // 题解 二分查找 + 回溯 + 剪枝
public:
    bool backtrack(vector<int> &jobs, vector<int> &workloads, int idx, int limit) {
        if (idx >= jobs.size()) { // 按这个上限limit可以完成分配
            return true;
        }
        int cur = jobs[idx]; // 当前要分配的工作
        for (auto &workload : workloads) { // 遍历工人
            if (workload + cur <= limit) {
                workload += cur;
                if (backtrack(jobs, workloads, idx + 1, limit)) { // 检查下一项任务
                    return true;
                }
                workload -= cur;   // 回溯
            }
            // 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
            // 或者当前工作恰能使该工人的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (workload == 0 || workload + cur == limit) {
                break;
            }
            // 剩下的情况就是分配给当前的工人的任务超出limit 循环到下一个工人
        }
        return false; // 该limit方案对所有工人都无法成立
    }

    bool check(vector<int> &jobs, int k, int limit) {
        vector<int> workloads(k, 0); // 每个工人的工作量
        return backtrack(jobs, workloads, 0, limit); // 调用递归函数
    }

    int minimumTimeRequired(vector<int> &jobs, int k) {
        sort(jobs.begin(), jobs.end(), greater<>()); // 排序
        int l = jobs[0], r = accumulate(jobs.begin(), jobs.end(), 0);  // 下限是最大的工作量，上限是总工作量
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

class Solution3 {  // dp + 状态压缩
public:
    int minimumTimeRequired(vector<int> &jobs, int k) {
        int n = (int) jobs.size();  // 工作数量
        vector<int> sum(1 << n); // 工作分配状态集合
        for (int i = 1; i < (1 << n); i++) {
            int x = __builtin_ctz(i), y = i - (1 << x);
            sum[i] = sum[y] + jobs[x]; // 各个分配状态下已经分配的工作量

        }
        vector<vector<int>> dp(k, vector<int>(1 << n));
        for (int i = 0; i < (1 << n); i++) {
            dp[0][i] = sum[i];
        }

        for (int i = 1; i < k; i++) {  // 遍历工人
            for (int j = 0; j < (1 << n); j++) { // 遍历工作分配状态
                int minn = INT_MAX;
                for (int x = j; x; x = (x - 1) & j) { // 枚举 j 的全部子集
                    minn = min(minn, max(dp[i - 1][j - x], sum[x]));  // 第i个工人完成任务子集x，前i-1个工人完成剩下的j-x个工作
                }
                dp[i][j] = minn;
            }
        }
        return dp[k - 1][(1 << n) - 1];
    }
};

int main() {
    vector<int> w1{3, 2, 3};
    vector<int> w2{1, 2, 4, 7, 8};
    vector<int> w3{9899456, 8291115, 9477657, 9288480, 5146275, 7697968, 8573153, 3582365, 3758448, 9881935, 2420271,
                   4542202};
    Solution3 sol;
    cout << sol.minimumTimeRequired(w1, 3) << endl;
    cout << sol.minimumTimeRequired(w2, 2) << endl;
    cout << sol.minimumTimeRequired(w3, 9) << endl;
    return 0;
}